package pro.softzhang.algo.lc800;

import pro.softzhang.algo.common.TrieNode;
import pro.softzhang.algo.flag.book.BOfferS;
import pro.softzhang.algo.flag.knowledge.KPrefixTree;

/**
 *
 */
@BOfferS
@KPrefixTree
public class LC820_ShortEncodingOfWords {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public int minimumLengthEncoding(String[] words) {
            TrieNode root = buildTrie(words);
            int total[] = {0};
            minimumLengthEncoding0(root, 1, total);
            return total[0];
        }

        private TrieNode buildTrie(String[] words) {
            TrieNode root = new TrieNode();
            for (String word : words) {
                TrieNode node = root;
                for (int i = word.length() - 1; i >= 0; i--) {
                    char ch = word.charAt(i);
                    if(node.children[ch - 'a'] == null) {
                        node.children[ch - 'a'] = new TrieNode();
                    }
                    node = node.children[ch - 'a'];
                }
            }
            return root;
        }

        private void minimumLengthEncoding0(TrieNode root, int length, int[] total) {
            boolean isLeaf = true;
            for (TrieNode child : root.children) {
                if(child != null) {
                    isLeaf = false;
                    minimumLengthEncoding0(child, length + 1, total);
                }
            }

            if(isLeaf) {
                total[0] += length;
            }
        }
    }
}
